#include <stdio.h>
#include <iostream>

using namespace std;

template <class T>
class Node{
public: 
    T data;
    Node<T> *next;  

    Node(){ next=NULL; }
    Node( const T &_data) 
    {
        data = _data; 
        next = NULL;
    }   
    
    ~Node(){ ;}
    
    Node  *getNext()const
    {
        return next;
    }   

    friend ostream & operator <<  ( ostream & out, const Node<T> & _n )
    {
        out << "data:" << _n.data <<" ,next: " << (bool) _n.next;
        return out;
    }
};


template <class T>
class List{
private:
    Node<T> *head;

public:
    List(){ head=NULL; }
    
    ~List()
    {
        cout << ">> Clean list data" << endl; 
        clean(); 
    }

    bool insert( const T &_in )
    {
        if ( head==NULL )
        {
            head = new Node<T> ( _in );
            return true;
        }
        
        Node<T> *tmp = head;
        head = new Node<T> ( _in );
        head->next = tmp;
        return true;
    }

    void traverse()const 
    {       
        Node<T> *next = head;
        while( next )
        {
            cout << next->data << endl;
            next = next->getNext();
        } 
    }

    Node<T> * find( const T &_in ) 
    {
        Node<T> *next = head;
        while ( next )
        {
            if ( next->data == _in )
            {
                return next;
            }            
            next = next->next; // advance one step
        }
        return NULL;
    }

    bool delNode( const T &_in )
    {
        Node<T> *next = head;
        
        // check if head is NULL
        if ( !next )
        {
            cout << ">> Empty list" << endl;
            return false;
        }
        
        // del head
        if ( next->data == _in )
        {
            head = head->next;
            delete next;
            
            return true;
        }
        
        // del rest nodes
        while ( next )
        {                                     
            // if reach end, stop
            if ( !next->next ) break;
            
            if ( next->next->data == _in )
            {
                Node<T> *tmp = next->next;
                next->next = tmp->next;// update previous's next
                delete tmp;
                
                return true;
            }

            next = next->next;         // advance one step
        }
      
        
        // if the data does not exist
        cout << ">> the required data does not exist" << endl;
        return false;       
    }
    
    
    void clean(void)
    {
        Node<T> *delMe = head;
        
        while( delMe )
        {
            head = delMe->next;  // update head
            delete delMe;
            delMe = head;        // advance one step
        }
    }  
};


int main()
{

    List<int> ll;
    int listSize = 1000;
    
    for(int i=0; i<listSize; i++)
    {
        ll.insert( i );
    }
    
    cout << "print the list data" << endl;
    ll.traverse();  
    
    // test find
    cout << ">> Test find " << endl;
    for(int i=listSize; i>=0; i--)
    {
        cout << "find test: " << i << endl;
        
        Node<int> *node = ll.find( i );
        //cout << "\t node ptr: " << node << endl;
        if ( node )
            cout << "\t" << node->data << endl;
    }
    
    cout << ">> clean list data " << endl;
    ll.clean();
    ll.traverse();
    
    for(int i=0; i<30; i++)
    {
        ll.insert( i );
    }
    
    // test delNode
    for(int i=40; i>=0; i--)
    {
        cout << "delete " << i << endl;
        ll.delNode( i );
        ll.traverse();
        cout << endl << endl;        
    } 

}
